{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove All Occurrences of a Substring"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeOccurrences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除一个字符串中所有出现的给定子字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串 <code>s</code> 和 <code>part</code> ，请你对 <code>s</code> 反复执行以下操作直到 <b>所有</b> 子字符串 <code>part</code> 都被删除：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>找到 <code>s</code> 中 <strong>最左边</strong> 的子字符串 <code>part</code> ，并将它从 <code>s</code> 中删除。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回从 <code>s</code> 中删除所有 <code>part</code> 子字符串以后得到的剩余字符串。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong> 是一个字符串中连续的字符序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"daabcbaabcbc\", part = \"abc\"\n",
    "<b>输出：</b>\"dab\"\n",
    "<b>解释：</b>以下操作按顺序执行：\n",
    "- s = \"da<strong>abc</strong>baabcbc\" ，删除下标从 2 开始的 \"abc\" ，得到 s = \"dabaabcbc\" 。\n",
    "- s = \"daba<strong>abc</strong>bc\" ，删除下标从 4 开始的 \"abc\" ，得到 s = \"dababc\" 。\n",
    "- s = \"dab<strong>abc</strong>\" ，删除下标从 3 开始的 \"abc\" ，得到 s = \"dab\" 。\n",
    "此时 s 中不再含有子字符串 \"abc\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"axxxxyyyyb\", part = \"xy\"\n",
    "<b>输出：</b>\"ab\"\n",
    "<b>解释：</b>以下操作按顺序执行：\n",
    "- s = \"axxx<strong>xy</strong>yyyb\" ，删除下标从 4 开始的 \"xy\" ，得到 s = \"axxxyyyb\" 。\n",
    "- s = \"axx<strong>xy</strong>yyb\" ，删除下标从 3 开始的 \"xy\" ，得到 s = \"axxyyb\" 。\n",
    "- s = \"ax<strong>xy</strong>yb\" ，删除下标从 2 开始的 \"xy\" ，得到 s = \"axyb\" 。\n",
    "- s = \"a<strong>xy</strong>b\" ，删除下标从 1 开始的 \"xy\" ，得到 s = \"ab\" 。\n",
    "此时 s 中不再含有子字符串 \"xy\" 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= part.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code>​​​​​​ 和 <code>part</code> 只包小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-all-occurrences-of-a-substring](https://leetcode.cn/problems/remove-all-occurrences-of-a-substring/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-all-occurrences-of-a-substring](https://leetcode.cn/problems/remove-all-occurrences-of-a-substring/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"daabcbaabcbc\"\\n\"abc\"', '\"axxxxyyyyb\"\\n\"xy\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        m = len(part)\n",
    "        res = \"\"\n",
    "        for ch in s:\n",
    "            # 模拟从左至右匹配的过程\n",
    "            res += ch\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "                res = res[:-m]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "#         i = 0\n",
    "#         j = 0\n",
    "#         n = len(s)\n",
    "#         k = len(part)\n",
    "#         if k>n:\n",
    "#             return s\n",
    "#         res = []\n",
    "#         temp = []\n",
    "#         for c in s:\n",
    "#             # print(c)\n",
    "#             if c == part[j]:\n",
    "#                 j+=1\n",
    "#             elif c==part[0]:\n",
    "#                 j=1\n",
    "#             else:\n",
    "#                 j=0\n",
    "#             if i>=len(res):\n",
    "#                 res.append(c)\n",
    "#                 temp.append(j)\n",
    "#             else:\n",
    "#                 res[i]=c\n",
    "#                 temp[i]=j\n",
    "                              \n",
    "#             i+=1\n",
    "            \n",
    "                \n",
    "            \n",
    "                \n",
    "#             if j==k:\n",
    "#                 i=i-k\n",
    "#                 j=temp[i-1] if i>0 else 0\n",
    "#             # print(i,j,temp,res)\n",
    "#         return ''.join(res[:i])\n",
    "            \n",
    "        n = len(s)\n",
    "        k = len(part)\n",
    "        res = \"\"\n",
    "        if k>n:\n",
    "            return s\n",
    "        for c in s:\n",
    "            res+=c\n",
    "            if res.endswith(part):\n",
    "                res = res[:-k]\n",
    "        return res\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n,m=len(s),len(part)\n",
    "        while True:\n",
    "            p=s.find(part)\n",
    "            if p==-1:\n",
    "                break\n",
    "            if p==0:\n",
    "                s=s[m::]\n",
    "            else:\n",
    "                s=s[0:p]+s[p+m::]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        st = ''\n",
    "        for c in s:\n",
    "            st += c\n",
    "            if(len(st) >= n and st[-n:] == part):\n",
    "                st = st[:-n]\n",
    "        return st\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(s)\n",
    "        np = len(part)\n",
    "        ks = s.find(part)\n",
    "        while ks>=0:\n",
    "            s = s[0:ks]+s[ks+np:]\n",
    "            ks = s.find(part)\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        ans = s\n",
    "        while ans.find(part) != -1:\n",
    "            ans = ans.replace(part, \"\", 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        # 模拟\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        ans = list(s)\n",
    "        while (id := ''.join(ans).find(part)) != -1:\n",
    "            n = len(ans)\n",
    "            tmp = []\n",
    "           \n",
    "            for i in range(id):\n",
    "                tmp.append(ans[i])\n",
    "            for i in range(id + len(part),n):\n",
    "                tmp.append(ans[i])\n",
    "            ans = tmp\n",
    "           \n",
    "                \n",
    "        return ''.join(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        res = ''\n",
    "        for ch in s:\n",
    "          res += ch\n",
    "          if len(res) >= n and res[-n:] == part:\n",
    "            res = res[:-n]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while (i := s.find(part)) != -1:\n",
    "            s = s[:i] + s[i + len(part):]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        ans = []\n",
    "        for c in s:\n",
    "            ans.append(c)\n",
    "            while len(ans) >= len(part) and ''.join(ans[-len(part):]) == part:\n",
    "                ans = ans[:-len(part)]\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "\n",
    "        \n",
    "        m = len(part)\n",
    "\n",
    "        res = \"\"\n",
    "\n",
    "        for ch in s:\n",
    "\n",
    "            res += ch\n",
    "\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "\n",
    "                res = res[:-m]\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        len_part = len(part)\n",
    "        len_s = len(s)\n",
    "        i = 0\n",
    "        while True:\n",
    "            if len_s < len_part or len_s - i < len_part:\n",
    "                break\n",
    "            if s[i:i+len_part] == part:\n",
    "                s = s[:i]+s[i+len_part:]\n",
    "                len_s -= len_part\n",
    "                i = 0\n",
    "                continue\n",
    "            i += 1\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "\n",
    "\n",
    "\n",
    "        m = len(part)\n",
    "\n",
    "        res = \"\"\n",
    "\n",
    "        for ch in s:\n",
    "\n",
    "            res += ch\n",
    "\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "\n",
    "                res = res[:-m]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        st = []\n",
    "        for i in s:\n",
    "            st.append(i)\n",
    "            if ''.join(st[-n:]) == part:\n",
    "                for _ in range(n):\n",
    "                    st.pop()\n",
    "\n",
    "        \n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        m = len(part)\n",
    "        res = \"\"\n",
    "        for ch in s:\n",
    "            res += ch\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "                res = res[:-m]\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def replace(self, s, part):\n",
    "        return s.replace(part, \"\", 1)\n",
    "\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = self.replace(s, part)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        res = ''\n",
    "        for ch in s:\n",
    "            res += ch\n",
    "            if len(res) >= n and res[-n:] == part:\n",
    "                res = res[:-n]\n",
    "        return res\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while True:\n",
    "            if s.find(part) != -1:\n",
    "                s = s.replace(part, '', 1)\n",
    "            else:\n",
    "                return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        L=len(part)\n",
    "        s=s+\".\"\n",
    "        def ret(s1,L1,part1):\n",
    "            for i in range(len(s1)-L1):\n",
    "                if s[i:i+L1] == part1:\n",
    "                    return s1[:i]+s1[i+L1:]\n",
    "        while part in  s:\n",
    "            s=ret(s,L,part)\n",
    "        return s[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while True:\n",
    "            tmp_idx = s.find(part)\n",
    "            if tmp_idx == -1:\n",
    "                return s\n",
    "            else:\n",
    "                s = s[:tmp_idx] + s[tmp_idx+len(part):]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, \"\", 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        res = \"\"\n",
    "        for c in s:\n",
    "            res += c\n",
    "            if res.endswith(part):\n",
    "                res = res[:len(res) - n]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "\n",
    "\n",
    "        m = len(part)\n",
    "\n",
    "        res = \"\"\n",
    "\n",
    "        for ch in s:\n",
    "\n",
    "            res += ch\n",
    "\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "                res = res[:-m]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        m = len(part)\n",
    "        res=''\n",
    "        for ch in s:\n",
    "            res+=ch\n",
    "            if len(res)>=m and res[-m:]==part:\n",
    "                res = res[:-m]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while True:\n",
    "            try:\n",
    "                index = s.index(part)\n",
    "                s = s[:index] + s[index+len(part):]\n",
    "            except:\n",
    "                return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while True:\n",
    "            if s.find(part) != -1:\n",
    "                s = s.replace(part, '', 1)\n",
    "            else:\n",
    "                break\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            idx = s.index(part)\n",
    "            s = s[:idx] + s[idx + len(part):]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        # replace\n",
    "        # while part in s:\n",
    "        #     s = s.replace(part,'')\n",
    "        #     print(s)\n",
    "        # return s\n",
    "\n",
    "\n",
    "        # 栈\n",
    "        stack = []\n",
    "        part = list(part)\n",
    "        n = len(part)\n",
    "        for ch in s:\n",
    "            stack.append(ch)\n",
    "            if len(stack) >= len(part):\n",
    "                while stack[len(stack)-len(part):] == part:\n",
    "                    for _ in range(len(part)):\n",
    "                        stack.pop()\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, \"\", 1)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            s = s.replace(part, '', 1)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        while part in s:\n",
    "            index = s.index(part)\n",
    "            s = s[:index] + s[index+len(part):]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        temp = \"\"\n",
    "        for i in s:\n",
    "            temp += i\n",
    "            if temp.endswith(part): \n",
    "                temp = temp[:-len(part)]\n",
    "        return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        # 情况1、s比part长度短\n",
    "        if len(s) < len(part):\n",
    "            return s\n",
    "        # 情况2、用栈处理\n",
    "        stk = []\n",
    "        for ch in s:\n",
    "            stk.append(ch)\n",
    "            if len(stk) >= len(part):\n",
    "                target = ''.join(stk[-len(part): ])\n",
    "                if target == part:\n",
    "                    stk[-len(part): ] = []\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        m = len(part)\n",
    "        pi1 = [0] * m   # part 的前缀数组\n",
    "        # 更新 part 的前缀数组\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and part[i] != part[j]:\n",
    "                j = pi1[j-1]\n",
    "            if part[i] == part[j]:\n",
    "                j += 1\n",
    "            pi1[i] = j\n",
    "        \n",
    "        res = []\n",
    "        pi2 = [0]   # res 的前缀数组\n",
    "        for ch in s:\n",
    "            # 模拟从左至右匹配的过程\n",
    "            res.append(ch)\n",
    "            # 更新 res 的前缀数组\n",
    "            j = pi2[-1]\n",
    "            while j > 0 and ch != part[j]:\n",
    "                j = pi1[j-1]\n",
    "            if ch == part[j]:\n",
    "                j += 1\n",
    "            pi2.append(j)\n",
    "            if j == m:\n",
    "                # 如果匹配成功，那么删去对应后缀\n",
    "                pi2[-m:] = []\n",
    "                res[-m:] = []\n",
    "        return \"\".join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        while True:\n",
    "            i = s.find(part)\n",
    "            if i == -1:\n",
    "                break\n",
    "            s = s[:i] + s[i+n:]\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 模拟 + 暴力匹配\n",
    "    def removeOccurrences1(self, s: str, part: str) -> str:\n",
    "        m = len(part)\n",
    "        res = \"\"\n",
    "        for ch in s:\n",
    "            # 模拟从左至右匹配的过程\n",
    "            res += ch\n",
    "            if len(res) >= m and res[-m:] == part:\n",
    "                # 如果匹配成功，那么删去对应后缀\n",
    "                res = res[:-m]\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        n = len(part)\n",
    "        while True:\n",
    "            i = s.find(part)\n",
    "            if i == -1:\n",
    "                break\n",
    "            \n",
    "            s = s[:i] + s[i + n:]\n",
    "\n",
    "        return s\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        if len(s) < len(part):\n",
    "            return s \n",
    "\n",
    "        i = 0\n",
    "        stack = []\n",
    "        while i < len(s):\n",
    "            stack.append(s[i])\n",
    "            if len(stack) >= len(part) and ''.join(stack[-len(part):]) == part:\n",
    "                stack = stack[:-len(part)]\n",
    "\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        stack = []\n",
    "        n = len(part)\n",
    "        for i in range(len(s)):\n",
    "            stack.append(s[i])\n",
    "            if len(stack)>=n:\n",
    "                if part == ''.join(stack[-n:]):\n",
    "                   for _ in range(n):\n",
    "                       stack.pop()\n",
    "        return ''.join(stack)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        #n = len(part)\n",
    "        #res = ''\n",
    "        #for ch in s:\n",
    "        #    res += ch\n",
    "        #    if len(res) >= n and res[-n:] == part:\n",
    "        #        res = res[:-n]\n",
    "        #return res\n",
    "    \n",
    "        n = len(part)\n",
    "        preSum = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "            while j > 0 and part[i] != part[j]:\n",
    "                j = preSum[j-1]\n",
    "            if part[i] == part[j]:\n",
    "                j += 1\n",
    "            preSum[i]= j\n",
    "        \n",
    "        res = []\n",
    "        lst = [0]\n",
    "        for ch in s:\n",
    "            res.append(ch)\n",
    "            j = lst[-1]\n",
    "            while j > 0 and ch != part[j]:\n",
    "                j = preSum[j-1]\n",
    "            if ch == part[j]:\n",
    "                j += 1\n",
    "            lst.append(j)\n",
    "            if j == n:\n",
    "                res[-n:] = []\n",
    "                lst[-n:] = []\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        stack = []\n",
    "        n = len(part)\n",
    "        for ch in s:\n",
    "            stack.append(ch)\n",
    "            if ''.join(stack[-n:]) == part:\n",
    "                for _ in range(n):\n",
    "                    stack.pop()\n",
    "        return ''.join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        # n = len(part)\n",
    "        # res = ''\n",
    "        # for ch in s:\n",
    "        #   res += ch\n",
    "        #   if len(res) >= n and res[-n:] == part:\n",
    "        #     res = res[:-n]\n",
    "        # return res\n",
    "\n",
    "        # KMP\n",
    "        n = len(part)\n",
    "        l1 = [0] * n\n",
    "        j = 0\n",
    "        for i in range(1, n):\n",
    "          while j > 0 and part[i] != part[j]:\n",
    "            j = l1[j-1]\n",
    "          if part[i] == part[j]:\n",
    "            j += 1\n",
    "          l1[i] = j\n",
    "        \n",
    "        res = []\n",
    "        p2 = [0]\n",
    "        for ch in s:\n",
    "          res.append(ch)\n",
    "          j = p2[-1]\n",
    "          while j > 0 and ch != part[j]:\n",
    "            j = l1[j-1]\n",
    "          if ch == part[j]:\n",
    "            j += 1\n",
    "          # p2 update\n",
    "          p2.append(j)\n",
    "          if j == n:\n",
    "            p2[-n:] = []\n",
    "            res[-n:] = []\n",
    "        return ''.join(res)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        # KMP algorithm\n",
    "        m = len(part)\n",
    "        pi1 = [0] * m\n",
    "        j = 0\n",
    "        for i in range(1, m):\n",
    "            while j > 0 and part[j] != part[i]:\n",
    "                j = pi1[j-1]\n",
    "            if part[j] == part[i]:\n",
    "                j += 1\n",
    "            pi1[i] = j\n",
    "        \n",
    "        res = []\n",
    "        pi2 = [0]\n",
    "        for ch in s:\n",
    "            res.append(ch)\n",
    "            j = pi2[-1]\n",
    "            while j > 0 and ch != part[j]:\n",
    "                j = pi1[j-1]\n",
    "            if ch == part[j]:\n",
    "                j += 1\n",
    "            pi2.append(j)\n",
    "            if j == m:\n",
    "                res[-m:] = []\n",
    "                pi2[-m:] = []\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, part: str) -> str:\n",
    "        dp = [-1]\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        m = len(part)\n",
    "        for i in range(n):\n",
    "\n",
    "            if dp[-1] == m - 2 and s[i] == part[-1]:\n",
    "                for _ in range(m - 1):\n",
    "                    dp.pop()\n",
    "                    ans.pop()\n",
    "            elif s[i] == part[dp[-1] + 1]:\n",
    "                dp.append(dp[-1] + 1)\n",
    "                ans.append(s[i])\n",
    "            else:\n",
    "                dp.append(0 if s[i] == part[0] else -1)\n",
    "                ans.append(s[i])\n",
    "        ans = ''.join(ans)\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i in range(len(ans) - m + 1):\n",
    "                if ans[i:i + m] == part:\n",
    "                    ans = ans[:i] + ans[i + m:]\n",
    "                    flag = True\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def removeOccurrences(self, s: str, p: str) -> str:\n",
    "        s, p = list(s), list(p)\n",
    "        n, m = len(s), len(p)\n",
    "        \n",
    "        nxt = [-1] * m\n",
    "        j = -1\n",
    "        for i in range(1, m):\n",
    "            while j >= 0 and p[j + 1] != p[i]: j = nxt[j]\n",
    "            if p[j + 1] == p[i]: j += 1\n",
    "            nxt[i] = j\n",
    "        \n",
    "        ans = []\n",
    "        nxt2 = [-1]\n",
    "        for i in range(n):\n",
    "            ans.append(s[i])\n",
    "            j = nxt2[-1]\n",
    "            while j >= 0 and p[j + 1] != ans[-1]: j = nxt[j]\n",
    "            if p[j + 1] == ans[-1]: j += 1\n",
    "            nxt2.append(j)\n",
    "            if j == m - 1:\n",
    "                nxt2[-m:] = []\n",
    "                ans[-m:] = []\n",
    "\n",
    "        return ''.join(ans)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
